hdu6715 算术

$\begin{aligned} &\sum_{i=1}^n\sum_{j=1}^m \mu(\text{lcm}(i,j)) \\ =&\sum_{d=1}^{\min(n,m)}\sum_{i=1}^n\sum_{j=1}^m [\gcd(i,j)=d]\mu(\frac{ij}{d})\\ =&\sum_{d=1}^{\min(n,m)}\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{d} \rfloor } [\gcd(i,j)=1]\mu(ijd)\\ =&\sum_{d=1}^{\min(n,m)} \sum_{t=1}^{\min(\lfloor \frac{n}{d} \rfloor,\lfloor \frac{m}{d} \rfloor)} \mu(t)\sum_{i=1}^{\lfloor \frac{n}{dt} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{dt} \rfloor } \mu(ijdt^2)\\ =&\sum_{T=1}^{\min(n,m)} \sum_{d|T} \mu(d)\sum_{i=1}^{\lfloor \frac{n}{T} \rfloor} \sum_{j=1}^{\lfloor \frac{m}{T} \rfloor} \mu(dTij)\\ =&\sum_{T=1}^{\min(n,m)} \sum_{i=1}^{\lfloor \frac{n}{T} \rfloor} \sum_{j=1}^{\lfloor \frac{m}{T} \rfloor} \mu(Tij)\\ =&\sum_{T=1}^{\min(n,m)} \mu(T) \sum_{i=1}^{\lfloor \frac{n}{T} \rfloor} \sum_{j=1}^{\lfloor \frac{m}{T} \rfloor} [\gcd(i,T)=1][\gcd(j,T)=1][\gcd(i,j)=1]\mu(i)\mu(j)\\ =&\sum_{T=1}^{\min(n,m)} \mu(T) \sum_{d=1}^{\min( \lfloor \frac{n}{T} \rfloor , \lfloor \frac{m}{T} \rfloor ) } \mu(d) [\gcd(d,T)=1] \sum_{i=1}^{\lfloor \frac{n}{Td} \rfloor} \sum_{j=1}^{\lfloor \frac{m}{Td} \rfloor} [\gcd(i,T)=1][\gcd(i,d)=1]\mu(i)\mu(d)[\gcd(j,T)=1][\gcd(j,d)=1]\mu(j)\mu(d)\\ =&\sum_{T=1}^{\min(n,m)} \sum_{d=1}^{\min( \lfloor \frac{n}{T} \rfloor , \lfloor \frac{m}{T} \rfloor ) } \mu(Td) \mu^2(d) \sum_{i=1}^{\lfloor \frac{n}{Td} \rfloor} \sum_{j=1}^{\lfloor \frac{m}{Td} \rfloor} [\gcd(i,dT)=1]\mu(i)[\gcd(j,dT)=1]\mu(j)\\ =&\sum_{T=1}^{\min(n,m)} \mu(T) \sum_{d|T} \mu^2(d) \sum_{i=1}^{\lfloor \frac{n}{T} \rfloor} \sum_{j=1}^{\lfloor \frac{m}{T} \rfloor} [\gcd(i,T)=1]\mu(i)[\gcd(j,T)=1]\mu(j)\\ =&\sum_{T=1}^{\min(n,m)} \mu(T) \left(\sum_{d|T} \mu^2(d) \right) \left(\sum_{i=1}^{\lfloor \frac{n}{T} \rfloor}[\gcd(i,T)=1]\mu(i) \right) \left( \sum_{j=1}^{\lfloor \frac{m}{T} \rfloor} [\gcd(j,T)=1]\mu(j) \right)\\ =&\sum_{T=1}^{\min(n,m)} \mu(T) \left(\sum_{d|T} \mu^2(d) \right) \left(\sum_{i=1}^{\lfloor \frac{n}{T} \rfloor}\mu(iT) \right) \left( \sum_{j=1}^{\lfloor \frac{m}{T} \rfloor} \mu(jT) \right) \\ \end{aligned}$

线筛出 $\sum_{d|T} \mu^2(d)$ 后直接暴力计算，复杂度 $\mathcal O(Tn \ln n)$

#include <cstdio>
#include <iostream>
using namespace std;

const int MAXN = 1e6 , Mod = 998244353;
int prnum , prime[ MAXN + 5 ] , mu[ MAXN + 5 ] , mu2[ MAXN + 5 ];
int lowk[ MAXN + 5 ] , loww[ MAXN + 5 ];
bool vis[ MAXN + 5 ];
void sieve( ) {
	mu[ 1 ] = 1; mu2[ 1 ] = 1;
	for( int i = 2 ; i <= MAXN ; i ++ ) {
		if( !vis[ i ] ) {
			prime[ ++ prnum ] = i;
			lowk[ i ] = i; loww[ i ] = 1;
			mu[ i ] = -1 , mu2[ i ] = 2;
		}
		for( int j = 1 ; j <= prnum && 1ll * i * prime[ j ] <= MAXN ; j ++ ) {
			vis[ i * prime[ j ] ] = 1;
			if( i % prime[ j ] == 0 ) {
				lowk[ i * prime[ j ] ] = lowk[ i ] * prime[ j ] , loww[ i * prime[ j ] ] = loww[ i ] + 1;
				mu2[ i * prime[ j ] ] = 1ll * mu2[ i / lowk[ i ] ] * ( loww[ i ] + 2 ) % Mod;
				break;
			}
			lowk[ i * prime[ j ] ] = prime[ j ] , loww[ i * prime[ j ] ] = 1;
			mu[ i * prime[ j ] ] = -mu[ i ];
			mu2[ i * prime[ j ] ] = mu2[ i ] * mu2[ prime[ j ] ];
		}
	}
}

int Calc( int n , int T ) {
	int Ans = 0;
	for( int i = 1 ; i <= n / T ; i ++ ) Ans += mu[ i * T ];
	return Ans;
}
int Solve( int n , int m ) {
	int Ans = 0;
	for( int i = 1 ; i <= min( n , m ) ; i ++ )
		if( mu[ i ] ) Ans = ( Ans + 1ll * mu[ i ] * mu2[ i ] * Calc( n , i ) * Calc( m , i ) % Mod ) % Mod;
	return ( Ans + Mod ) % Mod;
}

int T , n , m;
int main( ) {
	sieve();
	scanf("%d",&T);
	while( T -- ) {
		scanf("%d %d",&n,&m);
		printf("%d\n", Solve( n , m ) );
	}
	return 0;
}